<!DOCTYPE html>
<html lang="en"><head><script src="/livereload.js?mindelay=10&amp;v=2&amp;port=1313&amp;path=livereload" data-no-instant defer></script>
  <meta charset="utf-8" />
  <meta name="viewport" content="width=device-width, initial-scale=1.0" />
  <meta name="robots" content="noindex, nofollow" />
  <link rel="icon shortcut" href="/favicon.ico" sizes="32x32" />
<link rel="icon" href="/favicon.svg" type="image/svg+xml" />
<link rel="icon" href="/favicon-dark.svg" type="image/svg+xml" media="(prefers-color-scheme: dark)" />
<link rel="icon" href="/favicon-16x16.png" type="image/png" sizes="16x16" />
<link rel="icon" href="/favicon-32x32.png" type="image/png" sizes="32x32" />
<link rel="apple-touch-icon" href="/apple-touch-icon.png" sizes="180x180" />
<link fetchpriority="low" href="/site.webmanifest" rel="manifest" />

  <title>第 27 章：SP-GiST – PostgreSQL 14 Internals</title>
  <meta name="description" content="27.1 总览 SP-GiST 名称中的首字母代表空间划分。这里的空间被理解为执行搜索的任意值集合；它不必是常规意义上的空间 (比如二维平面)。名称中的 GiST 部分暗示了 GiST 和 SP-GiST 方法之间的某种相似性：它们都是广义搜索树，并作为索引各种数据类型的框架。
SP-GiST 方法背后的思想 1 是将搜索空间分割成几个非重叠的区域，这些区域又可以递归地分割成子区域。这样的划分产生了非平衡树 (与 B 树和 GiST 不同)，可以用来实现诸如四叉树、k-D 树和基数树 (字典树) 等众所周知的结构。
非平衡树通常分支较少，因此深度较大。例如，一个四叉树节点最多有四个子节点，而一个 k-D 树节点只能有两个。如果树保留在内存中，这并不会引起任何问题；但是当存储在磁盘上时，树节点必须尽可能密集地打包进页面以最小化 I/O，这项任务并不是那么简单。B 树和 GiST 索引不需要处理这个问题，因为它们的每个树节点都占据整个页面。
SP-GiST 树的内部节点包含一个满足其所有子节点条件的值。这样的值通常称为前缀；它与 GiST 索引中的谓词扮演着相同的角色。指向 SP-GiST 子节点的指针可能含有标签。
叶节点元素包含一个索引值 (或它的一部分) 以及相应的 TID。
就像 GiST 一样，SP-GiST 访问方法仅实现主要算法，诸如并发访问、锁和日志记录等底层细节。新的空间划分算法和数据类型可以通过操作符类接口添加。操作符类提供大部分逻辑，并定义了许多索引方面的功能。
在 SP-GiST 中，搜索从根节点开始，2 深度优先。通过 consistency 函数来选择值得下降的节点，与 GiST 中使用的 consistency 函数类似。对于树的内部节点，这个函数返回一组其值与搜索谓词不矛盾的子节点。consistency 函数不会下降到这些节点：它仅仅评估相应的标签和前缀。对于叶节点，它判断该节点的索引值是否与搜索谓词匹配。
在非平衡树中，搜索时间会因为分支的深度而有所不同。
有两个支持函数参与将值插入到 SP-GiST 索引中。当从根节点开始遍历树时，choose 函数会做出以下决策之一：将新值发给一个现有的子节点，为该值创建一个新的子节点，或者分裂当前节点 (如果这个值与当前节点的前缀不匹配)。如果选定的叶子页面没有足够的空间，picksplit 函数用于决定哪些节点应该移动到新页面。
现在我将提供一些示例来说明这些算法。
27.2 点的四叉树 四叉树用于在二维平面上索引点。平面根据选定点被递归地分割成四个区域 (象限)。" />

  
    <link rel="canonical" href="//localhost:1313/docs/chapter27/" itemprop="url" />
  

  

<meta property="og:title" content="第 27 章：SP-GiST" />
<meta property="og:description" content="" />
<meta property="og:type" content="website" />
<meta property="og:url" content="//localhost:1313/docs/chapter27/" />

  
  <meta itemprop="name" content="第 27 章：SP-GiST">
  <meta itemprop="description" content="27.1 总览 SP-GiST 名称中的首字母代表空间划分。这里的空间被理解为执行搜索的任意值集合；它不必是常规意义上的空间 (比如二维平面)。名称中的 GiST 部分暗示了 GiST 和 SP-GiST 方法之间的某种相似性：它们都是广义搜索树，并作为索引各种数据类型的框架。
SP-GiST 方法背后的思想 1 是将搜索空间分割成几个非重叠的区域，这些区域又可以递归地分割成子区域。这样的划分产生了非平衡树 (与 B 树和 GiST 不同)，可以用来实现诸如四叉树、k-D 树和基数树 (字典树) 等众所周知的结构。
非平衡树通常分支较少，因此深度较大。例如，一个四叉树节点最多有四个子节点，而一个 k-D 树节点只能有两个。如果树保留在内存中，这并不会引起任何问题；但是当存储在磁盘上时，树节点必须尽可能密集地打包进页面以最小化 I/O，这项任务并不是那么简单。B 树和 GiST 索引不需要处理这个问题，因为它们的每个树节点都占据整个页面。
SP-GiST 树的内部节点包含一个满足其所有子节点条件的值。这样的值通常称为前缀；它与 GiST 索引中的谓词扮演着相同的角色。指向 SP-GiST 子节点的指针可能含有标签。
叶节点元素包含一个索引值 (或它的一部分) 以及相应的 TID。
就像 GiST 一样，SP-GiST 访问方法仅实现主要算法，诸如并发访问、锁和日志记录等底层细节。新的空间划分算法和数据类型可以通过操作符类接口添加。操作符类提供大部分逻辑，并定义了许多索引方面的功能。
在 SP-GiST 中，搜索从根节点开始，2 深度优先。通过 consistency 函数来选择值得下降的节点，与 GiST 中使用的 consistency 函数类似。对于树的内部节点，这个函数返回一组其值与搜索谓词不矛盾的子节点。consistency 函数不会下降到这些节点：它仅仅评估相应的标签和前缀。对于叶节点，它判断该节点的索引值是否与搜索谓词匹配。
在非平衡树中，搜索时间会因为分支的深度而有所不同。
有两个支持函数参与将值插入到 SP-GiST 索引中。当从根节点开始遍历树时，choose 函数会做出以下决策之一：将新值发给一个现有的子节点，为该值创建一个新的子节点，或者分裂当前节点 (如果这个值与当前节点的前缀不匹配)。如果选定的叶子页面没有足够的空间，picksplit 函数用于决定哪些节点应该移动到新页面。
现在我将提供一些示例来说明这些算法。
27.2 点的四叉树 四叉树用于在二维平面上索引点。平面根据选定点被递归地分割成四个区域 (象限)。">
  <meta itemprop="wordCount" content="1094">
  <meta name="twitter:card" content="summary">
  <meta name="twitter:title" content="第 27 章：SP-GiST">
  <meta name="twitter:description" content="27.1 总览 SP-GiST 名称中的首字母代表空间划分。这里的空间被理解为执行搜索的任意值集合；它不必是常规意义上的空间 (比如二维平面)。名称中的 GiST 部分暗示了 GiST 和 SP-GiST 方法之间的某种相似性：它们都是广义搜索树，并作为索引各种数据类型的框架。
SP-GiST 方法背后的思想 1 是将搜索空间分割成几个非重叠的区域，这些区域又可以递归地分割成子区域。这样的划分产生了非平衡树 (与 B 树和 GiST 不同)，可以用来实现诸如四叉树、k-D 树和基数树 (字典树) 等众所周知的结构。
非平衡树通常分支较少，因此深度较大。例如，一个四叉树节点最多有四个子节点，而一个 k-D 树节点只能有两个。如果树保留在内存中，这并不会引起任何问题；但是当存储在磁盘上时，树节点必须尽可能密集地打包进页面以最小化 I/O，这项任务并不是那么简单。B 树和 GiST 索引不需要处理这个问题，因为它们的每个树节点都占据整个页面。
SP-GiST 树的内部节点包含一个满足其所有子节点条件的值。这样的值通常称为前缀；它与 GiST 索引中的谓词扮演着相同的角色。指向 SP-GiST 子节点的指针可能含有标签。
叶节点元素包含一个索引值 (或它的一部分) 以及相应的 TID。
就像 GiST 一样，SP-GiST 访问方法仅实现主要算法，诸如并发访问、锁和日志记录等底层细节。新的空间划分算法和数据类型可以通过操作符类接口添加。操作符类提供大部分逻辑，并定义了许多索引方面的功能。
在 SP-GiST 中，搜索从根节点开始，2 深度优先。通过 consistency 函数来选择值得下降的节点，与 GiST 中使用的 consistency 函数类似。对于树的内部节点，这个函数返回一组其值与搜索谓词不矛盾的子节点。consistency 函数不会下降到这些节点：它仅仅评估相应的标签和前缀。对于叶节点，它判断该节点的索引值是否与搜索谓词匹配。
在非平衡树中，搜索时间会因为分支的深度而有所不同。
有两个支持函数参与将值插入到 SP-GiST 索引中。当从根节点开始遍历树时，choose 函数会做出以下决策之一：将新值发给一个现有的子节点，为该值创建一个新的子节点，或者分裂当前节点 (如果这个值与当前节点的前缀不匹配)。如果选定的叶子页面没有足够的空间，picksplit 函数用于决定哪些节点应该移动到新页面。
现在我将提供一些示例来说明这些算法。
27.2 点的四叉树 四叉树用于在二维平面上索引点。平面根据选定点被递归地分割成四个区域 (象限)。">

    <link href="/css/compiled/main.css" rel="stylesheet" />



  <link href="/css/custom.css" rel="stylesheet" />





  <script>
     
    const defaultTheme = 'light';

    const setDarkTheme = () => {
      document.documentElement.classList.add("dark");
      document.documentElement.style.colorScheme = "dark";
    }
    const setLightTheme = () => {
      document.documentElement.classList.remove("dark");
      document.documentElement.style.colorScheme = "light";
    }

    if ("color-theme" in localStorage) {
      localStorage.getItem("color-theme") === "dark" ? setDarkTheme() : setLightTheme();
    } else {
      defaultTheme === "dark" ? setDarkTheme() : setLightTheme();
      if (defaultTheme === "system") {
        window.matchMedia("(prefers-color-scheme: dark)").matches ? setDarkTheme() : setLightTheme();
      }
    }
  </script>

  
</head>
<body dir="ltr"><div class="nav-container hx-sticky hx-top-0 hx-z-20 hx-w-full hx-bg-transparent print:hx-hidden">
  <div class="nav-container-blur hx-pointer-events-none hx-absolute hx-z-[-1] hx-h-full hx-w-full hx-bg-white dark:hx-bg-dark hx-shadow-[0_2px_4px_rgba(0,0,0,.02),0_1px_0_rgba(0,0,0,.06)] contrast-more:hx-shadow-[0_0_0_1px_#000] dark:hx-shadow-[0_-1px_0_rgba(255,255,255,.1)_inset] contrast-more:dark:hx-shadow-[0_0_0_1px_#fff]"></div>

  <nav class="hx-mx-auto hx-flex hx-items-center hx-justify-end hx-gap-2 hx-h-16 hx-px-6 hx-max-w-[90rem]">
    <a class="hx-flex hx-items-center hover:hx-opacity-75 ltr:hx-mr-auto rtl:hx-ml-auto" href="/">
        <img class="hx-block dark:hx-hidden" src="/images/postgresql-elephant-in-potential.svg" alt="PostgreSQL 14 Internals" height="30" width="45" />
        <img class="hx-hidden dark:hx-block" src="/images/postgresql-elephant-in-power.svg" alt="PostgreSQL 14 Internals" height="30" width="45" />
        <span class="hx-mx-2 hx-font-extrabold hx-inline hx-select-none" title="PostgreSQL 14 Internals">PostgreSQL 14 Internals</span>
    </a><a
            title="Docs"
            href="/docs"
            
            class="hx-text-sm contrast-more:hx-text-gray-700 contrast-more:dark:hx-text-gray-100 hx-relative -hx-ml-2 hx-hidden hx-whitespace-nowrap hx-p-2 md:hx-inline-block hx-font-medium"
          >
            <span class="hx-text-center">Docs</span>
          </a><a
            title="About"
            href="/about"
            
            class="hx-text-sm contrast-more:hx-text-gray-700 contrast-more:dark:hx-text-gray-100 hx-relative -hx-ml-2 hx-hidden hx-whitespace-nowrap hx-p-2 md:hx-inline-block hx-text-gray-600 hover:hx-text-gray-800 dark:hx-text-gray-400 dark:hover:hx-text-gray-200"
          >
            <span class="hx-text-center">About</span>
          </a><a
            title="Contact ↗"
            href="https://github.com/xiongcccc"
            target="_blank" rel="noreferer"
            class="hx-text-sm contrast-more:hx-text-gray-700 contrast-more:dark:hx-text-gray-100 hx-relative -hx-ml-2 hx-hidden hx-whitespace-nowrap hx-p-2 md:hx-inline-block hx-text-gray-600 hover:hx-text-gray-800 dark:hx-text-gray-400 dark:hover:hx-text-gray-200"
          >
            <span class="hx-text-center">Contact ↗</span>
          </a><div class="search-wrapper hx-relative md:hx-w-64">
  <div class="hx-relative hx-flex hx-items-center hx-text-gray-900 contrast-more:hx-text-gray-800 dark:hx-text-gray-300 contrast-more:dark:hx-text-gray-300">
    <input
      placeholder="Search..."
      class="search-input hx-block hx-w-full hx-appearance-none hx-rounded-lg hx-px-3 hx-py-2 hx-transition-colors hx-text-base hx-leading-tight md:hx-text-sm hx-bg-black/[.05] dark:hx-bg-gray-50/10 focus:hx-bg-white dark:focus:hx-bg-dark placeholder:hx-text-gray-500 dark:placeholder:hx-text-gray-400 contrast-more:hx-border contrast-more:hx-border-current"
      type="search"
      value=""
      spellcheck="false"
    />
    <kbd
      class="hx-absolute hx-my-1.5 hx-select-none ltr:hx-right-1.5 rtl:hx-left-1.5 hx-h-5 hx-rounded hx-bg-white hx-px-1.5 hx-font-mono hx-text-[10px] hx-font-medium hx-text-gray-500 hx-border dark:hx-border-gray-100/20 dark:hx-bg-dark/50 contrast-more:hx-border-current contrast-more:hx-text-current contrast-more:dark:hx-border-current hx-items-center hx-gap-1 hx-transition-opacity hx-pointer-events-none hx-hidden sm:hx-flex"
    >
      CTRL K
    </kbd>
  </div>

  <div>
    <ul
      class="search-results hextra-scrollbar hx-hidden hx-border hx-border-gray-200 hx-bg-white hx-text-gray-100 dark:hx-border-neutral-800 dark:hx-bg-neutral-900 hx-absolute hx-top-full hx-z-20 hx-mt-2 hx-overflow-auto hx-overscroll-contain hx-rounded-xl hx-py-2.5 hx-shadow-xl hx-max-h-[min(calc(50vh-11rem-env(safe-area-inset-bottom)),400px)] md:hx-max-h-[min(calc(100vh-5rem-env(safe-area-inset-bottom)),400px)] hx-inset-x-0 ltr:md:hx-left-auto rtl:md:hx-right-auto contrast-more:hx-border contrast-more:hx-border-gray-900 contrast-more:dark:hx-border-gray-50 hx-w-screen hx-min-h-[100px] hx-max-w-[min(calc(100vw-2rem),calc(100%+20rem))]"
      style="transition: max-height 0.2s ease 0s;"
    ></ul>
  </div>
</div>

          <a class="hx-p-2 hx-text-current" target="_blank" rel="noreferer" href="https://github.com/xiongcccc/xiongcccc.github.io" title="GitHub"><svg height=24 fill="currentColor" viewBox="3 3 18 18">
  <path d="M12 3C7.0275 3 3 7.12937 3 12.2276C3 16.3109 5.57625 19.7597 9.15374 20.9824C9.60374 21.0631 9.77249 20.7863 9.77249 20.5441C9.77249 20.3249 9.76125 19.5982 9.76125 18.8254C7.5 19.2522 6.915 18.2602 6.735 17.7412C6.63375 17.4759 6.19499 16.6569 5.8125 16.4378C5.4975 16.2647 5.0475 15.838 5.80124 15.8264C6.51 15.8149 7.01625 16.4954 7.18499 16.7723C7.99499 18.1679 9.28875 17.7758 9.80625 17.5335C9.885 16.9337 10.1212 16.53 10.38 16.2993C8.3775 16.0687 6.285 15.2728 6.285 11.7432C6.285 10.7397 6.63375 9.9092 7.20749 9.26326C7.1175 9.03257 6.8025 8.08674 7.2975 6.81794C7.2975 6.81794 8.05125 6.57571 9.77249 7.76377C10.4925 7.55615 11.2575 7.45234 12.0225 7.45234C12.7875 7.45234 13.5525 7.55615 14.2725 7.76377C15.9937 6.56418 16.7475 6.81794 16.7475 6.81794C17.2424 8.08674 16.9275 9.03257 16.8375 9.26326C17.4113 9.9092 17.76 10.7281 17.76 11.7432C17.76 15.2843 15.6563 16.0687 13.6537 16.2993C13.98 16.5877 14.2613 17.1414 14.2613 18.0065C14.2613 19.2407 14.25 20.2326 14.25 20.5441C14.25 20.7863 14.4188 21.0746 14.8688 20.9824C16.6554 20.364 18.2079 19.1866 19.3078 17.6162C20.4077 16.0457 20.9995 14.1611 21 12.2276C21 7.12937 16.9725 3 12 3Z"></path>
</svg>
<span class="hx-sr-only">GitHub</span>
          </a>
          <a class="hx-p-2 hx-text-current" target="_blank" rel="noreferer" href="https://twitter.com/" title="Twitter"><svg height=24 xmlns="http://www.w3.org/2000/svg" viewBox="0 0 512 512"><path fill="currentColor" d="M389.2 48h70.6L305.6 224.2 487 464H345L233.7 318.6 106.5 464H35.8L200.7 275.5 26.8 48H172.4L272.9 180.9 389.2 48zM364.4 421.8h39.1L151.1 88h-42L364.4 421.8z"/></svg><span class="hx-sr-only">Twitter</span>
          </a><button type="button" aria-label="Menu" class="hamburger-menu -hx-mr-2 hx-rounded hx-p-2 active:hx-bg-gray-400/20 md:hx-hidden"><svg height=24 fill="none" viewBox="0 0 24 24" stroke="currentColor"><g><path stroke-linecap="round" stroke-linejoin="round" stroke-width="2" d="M4 8H20"></path></g><g><path stroke-linecap="round" stroke-linejoin="round" stroke-width="2" d="M4 16H20"></path></g></svg></button>
  </nav>
</div>

  <div class='hx-mx-auto hx-flex hx-max-w-[90rem]'>
    <div class="mobile-menu-overlay [transition:background-color_1.5s_ease] hx-fixed hx-inset-0 hx-z-10 hx-bg-black/80 dark:hx-bg-black/60 hx-hidden"></div>
<aside class="sidebar-container hx-flex hx-flex-col print:hx-hidden md:hx-top-16 md:hx-shrink-0 md:hx-w-64 md:hx-self-start max-md:[transform:translate3d(0,-100%,0)] md:hx-sticky">
  
  <div class="hx-px-4 hx-pt-4 md:hx-hidden">
    <div class="search-wrapper hx-relative md:hx-w-64">
  <div class="hx-relative hx-flex hx-items-center hx-text-gray-900 contrast-more:hx-text-gray-800 dark:hx-text-gray-300 contrast-more:dark:hx-text-gray-300">
    <input
      placeholder="Search..."
      class="search-input hx-block hx-w-full hx-appearance-none hx-rounded-lg hx-px-3 hx-py-2 hx-transition-colors hx-text-base hx-leading-tight md:hx-text-sm hx-bg-black/[.05] dark:hx-bg-gray-50/10 focus:hx-bg-white dark:focus:hx-bg-dark placeholder:hx-text-gray-500 dark:placeholder:hx-text-gray-400 contrast-more:hx-border contrast-more:hx-border-current"
      type="search"
      value=""
      spellcheck="false"
    />
    <kbd
      class="hx-absolute hx-my-1.5 hx-select-none ltr:hx-right-1.5 rtl:hx-left-1.5 hx-h-5 hx-rounded hx-bg-white hx-px-1.5 hx-font-mono hx-text-[10px] hx-font-medium hx-text-gray-500 hx-border dark:hx-border-gray-100/20 dark:hx-bg-dark/50 contrast-more:hx-border-current contrast-more:hx-text-current contrast-more:dark:hx-border-current hx-items-center hx-gap-1 hx-transition-opacity hx-pointer-events-none hx-hidden sm:hx-flex"
    >
      CTRL K
    </kbd>
  </div>

  <div>
    <ul
      class="search-results hextra-scrollbar hx-hidden hx-border hx-border-gray-200 hx-bg-white hx-text-gray-100 dark:hx-border-neutral-800 dark:hx-bg-neutral-900 hx-absolute hx-top-full hx-z-20 hx-mt-2 hx-overflow-auto hx-overscroll-contain hx-rounded-xl hx-py-2.5 hx-shadow-xl hx-max-h-[min(calc(50vh-11rem-env(safe-area-inset-bottom)),400px)] md:hx-max-h-[min(calc(100vh-5rem-env(safe-area-inset-bottom)),400px)] hx-inset-x-0 ltr:md:hx-left-auto rtl:md:hx-right-auto contrast-more:hx-border contrast-more:hx-border-gray-900 contrast-more:dark:hx-border-gray-50 hx-w-screen hx-min-h-[100px] hx-max-w-[min(calc(100vw-2rem),calc(100%+20rem))]"
      style="transition: max-height 0.2s ease 0s;"
    ></ul>
  </div>
</div>

  </div>
  <div class="hextra-scrollbar hx-overflow-y-auto hx-overflow-x-hidden hx-p-4 hx-grow md:hx-h-[calc(100vh-var(--navbar-height)-var(--menu-height))]">
    <ul class="hx-flex hx-flex-col hx-gap-1 md:hx-hidden">
      
      
          <li class=""><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/about/"
    
  >About
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/"
    
  >Docs
        <span class="hextra-sidebar-collapsible-button"><svg fill="none" viewBox="0 0 24 24" stroke="currentColor" class="hx-h-[18px] hx-min-w-[18px] hx-rounded-sm hx-p-0.5 hover:hx-bg-gray-800/5 dark:hover:hx-bg-gray-100/5"><path stroke-linecap="round" stroke-linejoin="round" stroke-width="2" d="M9 5l7 7-7 7" class="hx-origin-center hx-transition-transform rtl:-hx-rotate-180"></path></svg></span>
    </a><div class="ltr:hx-pr-0 hx-overflow-hidden">
        <ul class='hx-relative hx-flex hx-flex-col hx-gap-1 before:hx-absolute before:hx-inset-y-1 before:hx-w-px before:hx-bg-gray-200 before:hx-content-[""] ltr:hx-ml-3 ltr:hx-pl-3 ltr:before:hx-left-0 rtl:hx-mr-3 rtl:hx-pr-3 rtl:before:hx-right-0 dark:before:hx-bg-neutral-800'><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter01/"
    
  >第 1 章：介绍
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter02/"
    
  >第 2 章：隔离性
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter03/"
    
  >第 3 章：页与元组
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter04/"
    
  >第 4 章：快照
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter05/"
    
  >第 5 章：页剪枝与 HOT 更新
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter06/"
    
  >第 6 章：Vacuum 与 Autovacuum
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter07/"
    
  >第 7 章：冻结
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter08/"
    
  >第 8 章：重建表与索引
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter09/"
    
  >第 9 章：缓冲区缓存
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter10/"
    
  >第 10 章：预写式日志
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter11/"
    
  >第 11 章：WAL 模式
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter12/"
    
  >第 12 章：关系级锁
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter13/"
    
  >第 13 章：行级锁
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter14/"
    
  >第 14 章：多样的锁
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter15/"
    
  >第 15 章：内存结构上的锁
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter16/"
    
  >第 16 章：查询执行阶段
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter17/"
    
  >第 17 章：统计信息
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter18/"
    
  >第 18 章：表访问方法
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter19/"
    
  >第 19 章：索引访问方法
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter20/"
    
  >第 20 章：索引扫描
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter21/"
    
  >第 21 章：嵌套循环
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter22/"
    
  >第 22 章：哈希
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter23/"
    
  >第 23 章：排序与归并
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter24/"
    
  >第 24 章：Hash
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter25/"
    
  >第 25 章：B-tree
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter26/"
    
  >第 26 章：GiST
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      sidebar-active-item hx-bg-primary-100 hx-font-semibold hx-text-primary-800 contrast-more:hx-border contrast-more:hx-border-primary-500 dark:hx-bg-primary-400/10 dark:hx-text-primary-600 contrast-more:dark:hx-border-primary-500"
    href="/docs/chapter27/"
    
  >第 27 章：SP-GiST
    </a>
  
    <ul class='hx-flex hx-flex-col hx-gap-1 hx-relative before:hx-absolute before:hx-inset-y-1 before:hx-w-px before:hx-bg-gray-200 before:hx-content-[""] dark:before:hx-bg-neutral-800 ltr:hx-pl-3 ltr:before:hx-left-0 rtl:hx-pr-3 rtl:before:hx-right-0 ltr:hx-ml-3 rtl:hx-mr-3'><li>
              <a
                href="#271-%e6%80%bb%e8%a7%88"
                class="hx-flex hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [word-break:break-word] hx-cursor-pointer [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] contrast-more:hx-border hx-gap-2 before:hx-opacity-25 before:hx-content-['#'] hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:hx-text-gray-900 contrast-more:dark:hx-text-gray-50 contrast-more:hx-border-transparent contrast-more:hover:hx-border-gray-900 contrast-more:dark:hover:hx-border-gray-50"
              >27.1 总览</a>
            </li>
          <li>
              <a
                href="#272-%e7%82%b9%e7%9a%84%e5%9b%9b%e5%8f%89%e6%a0%91"
                class="hx-flex hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [word-break:break-word] hx-cursor-pointer [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] contrast-more:hx-border hx-gap-2 before:hx-opacity-25 before:hx-content-['#'] hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:hx-text-gray-900 contrast-more:dark:hx-text-gray-50 contrast-more:hx-border-transparent contrast-more:hover:hx-border-gray-900 contrast-more:dark:hover:hx-border-gray-50"
              >27.2 点的四叉树</a>
            </li>
          <li>
              <a
                href="#273-%e7%82%b9%e7%9a%84-k-%e7%bb%b4%e6%a0%91"
                class="hx-flex hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [word-break:break-word] hx-cursor-pointer [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] contrast-more:hx-border hx-gap-2 before:hx-opacity-25 before:hx-content-['#'] hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:hx-text-gray-900 contrast-more:dark:hx-text-gray-50 contrast-more:hx-border-transparent contrast-more:hover:hx-border-gray-900 contrast-more:dark:hover:hx-border-gray-50"
              >27.3 点的 K 维树</a>
            </li>
          <li>
              <a
                href="#274-%e5%ad%97%e7%ac%a6%e4%b8%b2%e7%9a%84%e5%9f%ba%e6%95%b0%e6%a0%91"
                class="hx-flex hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [word-break:break-word] hx-cursor-pointer [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] contrast-more:hx-border hx-gap-2 before:hx-opacity-25 before:hx-content-['#'] hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:hx-text-gray-900 contrast-more:dark:hx-text-gray-50 contrast-more:hx-border-transparent contrast-more:hover:hx-border-gray-900 contrast-more:dark:hover:hx-border-gray-50"
              >27.4 字符串的基数树</a>
            </li>
          <li>
              <a
                href="#275-%e5%85%b6%e4%bb%96%e6%95%b0%e6%8d%ae%e7%b1%bb%e5%9e%8b"
                class="hx-flex hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [word-break:break-word] hx-cursor-pointer [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] contrast-more:hx-border hx-gap-2 before:hx-opacity-25 before:hx-content-['#'] hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:hx-text-gray-900 contrast-more:dark:hx-text-gray-50 contrast-more:hx-border-transparent contrast-more:hover:hx-border-gray-900 contrast-more:dark:hover:hx-border-gray-50"
              >27.5 其他数据类型</a>
            </li>
          </ul>
  
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter28/"
    
  >第 28 章：GIN
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter29/"
    
  >第 29 章：BRIN
    </a>
              
            </li><li class="hx-flex hx-flex-col open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter30/"
    
  >结论
    </a>
              
            </li></ul>
      </div></li>
          <li class=""><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/recommend/"
    
  >Recommend
    </a></li>
    </ul>

    <ul class="hx-flex hx-flex-col hx-gap-1 max-md:hx-hidden">
        
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter01/"
    
  >第 1 章：介绍
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter02/"
    
  >第 2 章：隔离性
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter03/"
    
  >第 3 章：页与元组
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter04/"
    
  >第 4 章：快照
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter05/"
    
  >第 5 章：页剪枝与 HOT 更新
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter06/"
    
  >第 6 章：Vacuum 与 Autovacuum
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter07/"
    
  >第 7 章：冻结
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter08/"
    
  >第 8 章：重建表与索引
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter09/"
    
  >第 9 章：缓冲区缓存
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter10/"
    
  >第 10 章：预写式日志
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter11/"
    
  >第 11 章：WAL 模式
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter12/"
    
  >第 12 章：关系级锁
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter13/"
    
  >第 13 章：行级锁
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter14/"
    
  >第 14 章：多样的锁
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter15/"
    
  >第 15 章：内存结构上的锁
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter16/"
    
  >第 16 章：查询执行阶段
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter17/"
    
  >第 17 章：统计信息
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter18/"
    
  >第 18 章：表访问方法
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter19/"
    
  >第 19 章：索引访问方法
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter20/"
    
  >第 20 章：索引扫描
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter21/"
    
  >第 21 章：嵌套循环
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter22/"
    
  >第 22 章：哈希
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter23/"
    
  >第 23 章：排序与归并
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter24/"
    
  >第 24 章：Hash
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter25/"
    
  >第 25 章：B-tree
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter26/"
    
  >第 26 章：GiST
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      sidebar-active-item hx-bg-primary-100 hx-font-semibold hx-text-primary-800 contrast-more:hx-border contrast-more:hx-border-primary-500 dark:hx-bg-primary-400/10 dark:hx-text-primary-600 contrast-more:dark:hx-border-primary-500"
    href="/docs/chapter27/"
    
  >第 27 章：SP-GiST
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter28/"
    
  >第 28 章：GIN
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter29/"
    
  >第 29 章：BRIN
    </a></li>
          <li class="open"><a
    class="hx-flex hx-items-center hx-justify-between hx-gap-2 hx-cursor-pointer hx-rounded hx-px-2 hx-py-1.5 hx-text-sm hx-transition-colors [-webkit-tap-highlight-color:transparent] [-webkit-touch-callout:none] [word-break:break-word]
      hx-text-gray-500 hover:hx-bg-gray-100 hover:hx-text-gray-900 contrast-more:hx-border contrast-more:hx-border-transparent contrast-more:hx-text-gray-900 contrast-more:hover:hx-border-gray-900 dark:hx-text-neutral-400 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50 contrast-more:dark:hx-text-gray-50 contrast-more:dark:hover:hx-border-gray-50"
    href="/docs/chapter30/"
    
  >结论
    </a></li>
        
      </ul>
    </div>
  
  
    <div class="  hx-sticky hx-bottom-0 hx-bg-white dark:hx-bg-dark hx-mx-4 hx-py-4 hx-shadow-[0_-12px_16px_#fff] hx-flex hx-items-center hx-gap-2 dark:hx-border-neutral-800 dark:hx-shadow-[0_-12px_16px_#111] contrast-more:hx-border-neutral-400 contrast-more:hx-shadow-none contrast-more:dark:hx-shadow-none hx-border-t" data-toggle-animation="show"><div class="hx-flex hx-grow hx-flex-col"><button
  title="Change theme"
  data-theme="light"
  class="theme-toggle hx-group hx-h-7 hx-rounded-md hx-px-2 hx-text-left hx-text-xs hx-font-medium hx-text-gray-600 hx-transition-colors dark:hx-text-gray-400 hover:hx-bg-gray-100 hover:hx-text-gray-900 dark:hover:hx-bg-primary-100/5 dark:hover:hx-text-gray-50"
  type="button"
  aria-label="Change theme"
>
  <div class="hx-flex hx-items-center hx-gap-2 hx-capitalize"><svg height=12 class="group-data-[theme=light]:hx-hidden" xmlns="http://www.w3.org/2000/svg" fill="none" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" aria-hidden="true"><path stroke-linecap="round" stroke-linejoin="round" d="M12 3v1m0 16v1m9-9h-1M4 12H3m15.364 6.364l-.707-.707M6.343 6.343l-.707-.707m12.728 0l-.707.707M6.343 17.657l-.707.707M16 12a4 4 0 11-8 0 4 4 0 018 0z"/></svg><span class="group-data-[theme=light]:hx-hidden">Light</span><svg height=12 class="group-data-[theme=dark]:hx-hidden" xmlns="http://www.w3.org/2000/svg" fill="none" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" aria-hidden="true"><path stroke-linecap="round" stroke-linejoin="round" d="M20.354 15.354A9 9 0 018.646 3.646 9.003 9.003 0 0012 21a9.003 9.003 0 008.354-5.646z"/></svg><span class="group-data-[theme=dark]:hx-hidden">Dark</span></div>
</button>
</div></div></aside>
    
<nav class="hextra-toc hx-order-last hx-hidden hx-w-64 hx-shrink-0 xl:hx-block print:hx-hidden hx-px-4" aria-label="table of contents">
    <div class="hextra-scrollbar hx-sticky hx-top-16 hx-overflow-y-auto hx-pr-4 hx-pt-6 hx-text-sm [hyphens:auto] hx-max-h-[calc(100vh-var(--navbar-height)-env(safe-area-inset-bottom))] ltr:hx--mr-4 rtl:hx--ml-4"><p class="hx-mb-4 hx-font-semibold hx-tracking-tight">On this page</p><ul>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="hx-font-semibold hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#271-%e6%80%bb%e8%a7%88">27.1 总览
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="hx-font-semibold hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#272-%e7%82%b9%e7%9a%84%e5%9b%9b%e5%8f%89%e6%a0%91">27.2 点的四叉树
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="ltr:hx-pl-4 rtl:hx-pr-4 hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#2721-%e6%93%8d%e4%bd%9c%e7%ac%a6%e7%b1%bb">27.2.1 操作符类
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="ltr:hx-pl-4 rtl:hx-pr-4 hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#2722-%e9%a1%b5%e9%9d%a2%e5%b8%83%e5%b1%80">27.2.2 页面布局
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="ltr:hx-pl-4 rtl:hx-pr-4 hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#2723-%e6%90%9c%e7%b4%a2">27.2.3 搜索
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="ltr:hx-pl-4 rtl:hx-pr-4 hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#2724-%e6%8f%92%e5%85%a5">27.2.4 插入
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="ltr:hx-pl-4 rtl:hx-pr-4 hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#2725-%e5%b1%9e%e6%80%a7">27.2.5 属性
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="hx-font-semibold hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#273-%e7%82%b9%e7%9a%84-k-%e7%bb%b4%e6%a0%91">27.3 点的 K 维树
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="hx-font-semibold hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#274-%e5%ad%97%e7%ac%a6%e4%b8%b2%e7%9a%84%e5%9f%ba%e6%95%b0%e6%a0%91">27.4 字符串的基数树
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="ltr:hx-pl-4 rtl:hx-pr-4 hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#2741-%e6%93%8d%e4%bd%9c%e7%ac%a6%e7%b1%bb">27.4.1 操作符类
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="ltr:hx-pl-4 rtl:hx-pr-4 hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#2742-%e6%90%9c%e7%b4%a2">27.4.2 搜索
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="ltr:hx-pl-4 rtl:hx-pr-4 hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#2743-%e6%8f%92%e5%85%a5">27.4.3 插入
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="ltr:hx-pl-4 rtl:hx-pr-4 hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#2744-%e5%b1%9e%e6%80%a7">27.4.4 属性
        </a>
      </li>
      <li class="hx-my-2 hx-scroll-my-6 hx-scroll-py-6">
        <a class="hx-font-semibold hx-inline-block hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-300 contrast-more:hx-text-gray-900 contrast-more:hx-underline contrast-more:dark:hx-text-gray-50 hx-w-full hx-break-words" href="#275-%e5%85%b6%e4%bb%96%e6%95%b0%e6%8d%ae%e7%b1%bb%e5%9e%8b">27.5 其他数据类型
        </a>
      </li></ul>
      <div class="hx-mt-8 hx-border-t hx-bg-white hx-pt-8 hx-shadow-[0_-12px_16px_white] dark:hx-bg-dark dark:hx-shadow-[0_-12px_16px_#111] hx-sticky hx-bottom-0 hx-flex hx-flex-col hx-items-start hx-gap-2 hx-pb-8 dark:hx-border-neutral-800 contrast-more:hx-border-t contrast-more:hx-border-neutral-400 contrast-more:hx-shadow-none contrast-more:dark:hx-border-neutral-400">
        <button aria-hidden="true" id="backToTop" onClick="scrollUp();" class="hx-transition-all hx-duration-75 hx-opacity-0 hx-text-xs hx-font-medium hx-text-gray-500 hover:hx-text-gray-900 dark:hx-text-gray-400 dark:hover:hx-text-gray-100 contrast-more:hx-text-gray-800 contrast-more:dark:hx-text-gray-50">
          <span>Scroll to top</span>
          <svg xmlns="http://www.w3.org/2000/svg" fill="none" viewBox="0 0 24 24" stroke-width="1.5" stroke="currentColor" class="hx-inline ltr:hx-ml-1 rtl:hx-mr-1 hx-h-3.5 hx-w-3.5 hx-border hx-rounded-full hx-border-gray-500 hover:hx-border-gray-900 dark:hx-border-gray-400 dark:hover:hx-border-gray-100 contrast-more:hx-border-gray-800 contrast-more:dark:hx-border-gray-50">
            <path stroke-linecap="round" stroke-linejoin="round" d="M4.5 15.75l7.5-7.5 7.5 7.5" />
          </svg>
        </button>
      </div>
    </div>
  </nav>


    <article class="hx-w-full hx-break-words hx-flex hx-min-h-[calc(100vh-var(--navbar-height))] hx-min-w-0 hx-justify-center hx-pb-8 hx-pr-[calc(env(safe-area-inset-right)-1.5rem)]">
      <main class="hx-w-full hx-min-w-0 hx-max-w-6xl hx-px-6 hx-pt-4 md:hx-px-12">
        
  <div class="hx-mt-1.5 hx-flex hx-items-center hx-gap-1 hx-overflow-hidden hx-text-sm hx-text-gray-500 dark:hx-text-gray-400 contrast-more:hx-text-current">
        <div class="hx-whitespace-nowrap hx-transition-colors hx-min-w-[24px] hx-overflow-hidden hx-text-ellipsis hover:hx-text-gray-900 dark:hover:hx-text-gray-100">
          <a href="/docs/">Docs</a>
        </div><svg class="hx-w-3.5 hx-shrink-0 rtl:-hx-rotate-180" xmlns="http://www.w3.org/2000/svg" fill="none" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" aria-hidden="true"><path stroke-linecap="round" stroke-linejoin="round" d="M9 5l7 7-7 7"/></svg><div class="hx-whitespace-nowrap hx-transition-colors hx-font-medium hx-text-gray-700 contrast-more:hx-font-bold contrast-more:hx-text-current dark:hx-text-gray-100 contrast-more:dark:hx-text-current">第 27 章：SP-GiST</div>
  </div>

        <div class="content">
          <h1>第 27 章：SP-GiST</h1>
          <h2>27.1 总览<span class="hx-absolute -hx-mt-20" id="271-总览"></span>
    <a href="#271-%e6%80%bb%e8%a7%88" class="subheading-anchor" aria-label="Permalink for this section"></a></h2><p>SP-GiST 名称中的首字母代表空间划分。这里的空间被理解为执行搜索的任意值集合；它不必是常规意义上的空间 (比如二维平面)。名称中的 GiST 部分暗示了 GiST 和 SP-GiST 方法之间的某种相似性：它们都是广义搜索树，并作为索引各种数据类型的框架。</p>
<p>SP-GiST 方法背后的思想 <sup id="fnref:1"><a href="#fn:1" class="footnote-ref" role="doc-noteref">1</a></sup> 是将搜索空间分割成几个非重叠的区域，这些区域又可以递归地分割成子区域。这样的划分产生了非平衡树 (与 B 树和 GiST 不同)，可以用来实现诸如四叉树、k-D 树和基数树 (字典树) 等众所周知的结构。</p>
<p>非平衡树通常分支较少，因此深度较大。例如，一个四叉树节点最多有四个子节点，而一个 k-D 树节点只能有两个。如果树保留在内存中，这并不会引起任何问题；但是当存储在磁盘上时，树节点必须尽可能密集地打包进页面以最小化 I/O，这项任务并不是那么简单。B 树和 GiST 索引不需要处理这个问题，因为它们的每个树节点都占据整个页面。</p>
<p>SP-GiST 树的内部节点包含一个满足其所有子节点条件的值。这样的值通常称为前缀；它与 GiST 索引中的谓词扮演着相同的角色。指向 SP-GiST 子节点的指针可能含有标签。</p>
<p>叶节点元素包含一个索引值 (或它的一部分) 以及相应的 TID。</p>
<p>就像 GiST 一样，SP-GiST 访问方法仅实现主要算法，诸如并发访问、锁和日志记录等底层细节。新的空间划分算法和数据类型可以通过操作符类接口添加。操作符类提供大部分逻辑，并定义了许多索引方面的功能。</p>
<p>在 SP-GiST 中，搜索从根节点开始，<sup id="fnref:2"><a href="#fn:2" class="footnote-ref" role="doc-noteref">2</a></sup> 深度优先。通过 <em>consistency</em> 函数来选择值得下降的节点，与 GiST 中使用的 consistency 函数类似。对于树的内部节点，这个函数返回一组其值与搜索谓词不矛盾的子节点。consistency 函数不会下降到这些节点：它仅仅评估相应的标签和前缀。对于叶节点，它判断该节点的索引值是否与搜索谓词匹配。</p>
<p>在非平衡树中，搜索时间会因为分支的深度而有所不同。</p>
<p>有两个支持函数参与将值插入到 SP-GiST 索引中。当从根节点开始遍历树时，choose 函数会做出以下决策之一：将新值发给一个现有的子节点，为该值创建一个新的子节点，或者分裂当前节点 (如果这个值与当前节点的前缀不匹配)。如果选定的叶子页面没有足够的空间，picksplit 函数用于决定哪些节点应该移动到新页面。</p>
<p>现在我将提供一些示例来说明这些算法。</p>
<h2>27.2 点的四叉树<span class="hx-absolute -hx-mt-20" id="272-点的四叉树"></span>
    <a href="#272-%e7%82%b9%e7%9a%84%e5%9b%9b%e5%8f%89%e6%a0%91" class="subheading-anchor" aria-label="Permalink for this section"></a></h2><p>四叉树用于在二维平面上索引点。平面根据选定点被递归地分割成四个区域 (象限)。</p>
<p>这个点称为中心点；它作为节点前缀，即定义子值位置的条件。</p>
<p>根节点将平面分割成四个象限。</p>
<img src="27-1.png" style="width:80%; float:left" />
<div style="clear:both;"></div>
<p>然后，每个象限进一步分割成它自己的四个象限。</p>
<img src="27-2.png" style="width:80%; float:left" />
<div style="clear:both;"></div>
<p>这个过程持续进行，直到达到所需的区域数量。</p>
<img src="27-3.png" style="width:80%; float:left" />
<div style="clear:both;"></div>
<p>这个例子使用了基于 airports_big 表建立的索引。示意图显示，分支深度取决于相应象限中点的密度。为了可视化，我将 <span class="marginalia" data-note="80"><em>fillfactor</em></span> 存储参数设置为较小的值，这使得树的深度更深。</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; CREATE INDEX airports_quad_idx ON airports_big
</span></span><span class="line"><span class="cl">USING spgist<span class="o">(</span>coordinates<span class="o">)</span> WITH <span class="o">(</span><span class="nv">fillfactor</span> <span class="o">=</span> 10<span class="o">)</span><span class="p">;</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>点的默认操作符类是 quad_point_ops。</p>
<h3>27.2.1 操作符类<span class="hx-absolute -hx-mt-20" id="2721-操作符类"></span>
    <a href="#2721-%e6%93%8d%e4%bd%9c%e7%ac%a6%e7%b1%bb" class="subheading-anchor" aria-label="Permalink for this section"></a></h3><p>我已经提及了 SP-GiST 支持函数：<sup id="fnref:3"><a href="#fn:3" class="footnote-ref" role="doc-noteref">3</a></sup> 用于搜索的 consistency 函数和用于插入的 picksplit 函数。</p>
<p>现在，让我们看一下 quad_point_ops 操作符类的支持函数列表。<sup id="fnref:4"><a href="#fn:4" class="footnote-ref" role="doc-noteref">4</a></sup> 所有这些函数都是必须的。</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; SELECT amprocnum, amproc::regproc
</span></span><span class="line"><span class="cl">FROM pg_am am
</span></span><span class="line"><span class="cl">  JOIN pg_opclass opc ON <span class="nv">opcmethod</span> <span class="o">=</span> am.oid
</span></span><span class="line"><span class="cl">  JOIN pg_amproc amop ON <span class="nv">amprocfamily</span> <span class="o">=</span> opcfamily
</span></span><span class="line"><span class="cl">WHERE <span class="nv">amname</span> <span class="o">=</span> <span class="s1">&#39;spgist&#39;</span>
</span></span><span class="line"><span class="cl">AND <span class="nv">opcname</span> <span class="o">=</span> <span class="s1">&#39;quad_point_ops&#39;</span>
</span></span><span class="line"><span class="cl">ORDER BY amprocnum<span class="p">;</span>
</span></span><span class="line"><span class="cl"> amprocnum <span class="p">|</span>          amproc
</span></span><span class="line"><span class="cl">−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl">         <span class="m">1</span> <span class="p">|</span> spg_quad_config
</span></span><span class="line"><span class="cl">         <span class="m">2</span> <span class="p">|</span> spg_quad_choose
</span></span><span class="line"><span class="cl">         <span class="m">3</span> <span class="p">|</span> spg_quad_picksplit
</span></span><span class="line"><span class="cl">         <span class="m">4</span> <span class="p">|</span> spg_quad_inner_consistent
</span></span><span class="line"><span class="cl">         <span class="m">5</span> <span class="p">|</span> spg_quad_leaf_consistent
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">5</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>这些函数执行以下任务：</p>
<p>1 config 函数向访问方法报告操作符类的基本信息。</p>
<p>2 choose 函数选择要插入的节点。</p>
<p>3 picksplit 函数在页面分裂后，在页面之间分配节点。</p>
<p>4 inner_consistent 函数检查内部节点的值是否满足搜索谓词。</p>
<p>5 leaf_consistent 函数判断叶节点中存储的值是否满足搜索谓词。</p>
<p>还有几个可选的函数。</p>
<p>quad_point_ops 操作符类支持与 GiST 相同的策略：<sup id="fnref:5"><a href="#fn:5" class="footnote-ref" role="doc-noteref">5</a></sup></p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; SELECT amopopr::regoperator, oprcode::regproc, amopstrategy
</span></span><span class="line"><span class="cl">FROM pg_am am
</span></span><span class="line"><span class="cl">  JOIN pg_opclass opc ON <span class="nv">opcmethod</span> <span class="o">=</span> am.oid
</span></span><span class="line"><span class="cl">  JOIN pg_amop amop ON <span class="nv">amopfamily</span> <span class="o">=</span> opcfamily
</span></span><span class="line"><span class="cl">  JOIN pg_operator opr ON opr.oid <span class="o">=</span> amopopr
</span></span><span class="line"><span class="cl">WHERE <span class="nv">amname</span> <span class="o">=</span> <span class="s1">&#39;spgist&#39;</span>
</span></span><span class="line"><span class="cl">AND <span class="nv">opcname</span> <span class="o">=</span> <span class="s1">&#39;quad_point_ops&#39;</span>
</span></span><span class="line"><span class="cl">ORDER BY amopstrategy<span class="p">;</span>
</span></span><span class="line"><span class="cl">      amopopr     <span class="p">|</span>    oprcode     <span class="p">|</span> amopstrategy
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> &lt;&lt;<span class="o">(</span>point,point<span class="o">)</span>  <span class="p">|</span> point_left     <span class="p">|</span>            <span class="m">1</span>
</span></span><span class="line"><span class="cl"> &gt;&gt;<span class="o">(</span>point,point<span class="o">)</span>  <span class="p">|</span> point_right    <span class="p">|</span>            <span class="m">5</span>
</span></span><span class="line"><span class="cl"> ~<span class="o">=(</span>point,point<span class="o">)</span>  <span class="p">|</span> point_eq       <span class="p">|</span>            <span class="m">6</span>
</span></span><span class="line"><span class="cl"> &lt;@<span class="o">(</span>point,box<span class="o">)</span>    <span class="p">|</span> on_pb          <span class="p">|</span>            <span class="m">8</span>
</span></span><span class="line"><span class="cl"> &lt;&lt;<span class="p">|</span><span class="o">(</span>point,point<span class="o">)</span> <span class="p">|</span> point_below    <span class="p">|</span>           <span class="m">10</span>
</span></span><span class="line"><span class="cl"> <span class="p">|</span>&gt;&gt;<span class="o">(</span>point,point<span class="o">)</span> <span class="p">|</span> point_above    <span class="p">|</span>           <span class="m">11</span>
</span></span><span class="line"><span class="cl"> &lt;−&gt;<span class="o">(</span>point,point<span class="o">)</span> <span class="p">|</span> point_distance <span class="p">|</span>           <span class="m">15</span>
</span></span><span class="line"><span class="cl"> &lt;^<span class="o">(</span>point,point<span class="o">)</span>  <span class="p">|</span> point_below    <span class="p">|</span>           <span class="m">29</span>
</span></span><span class="line"><span class="cl"> &gt;^<span class="o">(</span>point,point<span class="o">)</span>  <span class="p">|</span> point_above    <span class="p">|</span>           <span class="m">30</span>
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">9</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>例如，你可以使用上述操作符 &gt;^ 来找出位于迪克森北部的机场。</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; SELECT airport_code, airport_name-&gt;&gt;<span class="s1">&#39;en&#39;</span>
</span></span><span class="line"><span class="cl">FROM airports_big
</span></span><span class="line"><span class="cl">WHERE coordinates &gt;^ <span class="s1">&#39;(80.3817,73.5167)&#39;</span>::point<span class="p">;</span>
</span></span><span class="line"><span class="cl"> airport_code <span class="p">|</span>          ?column?
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> THU          <span class="p">|</span> Thule Air Base
</span></span><span class="line"><span class="cl"> YEU          <span class="p">|</span> Eureka Airport
</span></span><span class="line"><span class="cl"> YLT          <span class="p">|</span> Alert Airport
</span></span><span class="line"><span class="cl"> YRB          <span class="p">|</span> Resolute Bay Airport
</span></span><span class="line"><span class="cl"> LYR          <span class="p">|</span> Svalbard Airport, Longyear
</span></span><span class="line"><span class="cl"> NAQ          <span class="p">|</span> Qaanaaq Airport
</span></span><span class="line"><span class="cl"> YGZ          <span class="p">|</span> Grise Fiord Airport
</span></span><span class="line"><span class="cl"> DKS          <span class="p">|</span> Dikson Airport
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">8</span> rows<span class="o">)</span>
</span></span><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN <span class="o">(</span>costs off<span class="o">)</span> SELECT airport_code
</span></span><span class="line"><span class="cl">FROM airports_big
</span></span><span class="line"><span class="cl">WHERE coordinates &gt;^ <span class="s1">&#39;(80.3817,73.5167)&#39;</span>::point<span class="p">;</span>
</span></span><span class="line"><span class="cl">                          QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl">Bitmap Heap Scan on airports_big
</span></span><span class="line"><span class="cl">  Recheck Cond: <span class="o">(</span>coordinates &gt;^ <span class="s1">&#39;(80.3817,73.5167)&#39;</span>::point<span class="o">)</span>
</span></span><span class="line"><span class="cl">  −&gt; Bitmap Index Scan on airports_quad_idx
</span></span><span class="line"><span class="cl">      Index Cond: <span class="o">(</span>coordinates &gt;^ <span class="s1">&#39;(80.3817,73.5167)&#39;</span>::point<span class="o">)</span>
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">4</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>让我们深入分析一下四叉树的结构和内部工作原理。我们将使用 GiST 章节中提到的相同例子，它包含几个点。</p>
<p>以下是在这种情况下如何划分平面的示意图：</p>
<img src="27-4.png" style="width:70%; float:left" />
<div style="clear:both;"></div>
<p>左边的插图展示了树的某一层级中象限的编号；为了清晰起见，接下来的插图中，我将按照相同的顺序从左到右放置子节点。位于边界上的点被划入编号较小的象限。右边的插图显示了最终的分区。</p>
<p>你可以在下面看到该索引可能的结构。每个内部节点最多引用四个子节点，每个指针都用象限号标记：</p>
<img src="27-5.png" style="width:70%; float:left" />
<div style="clear:both;"></div>
<h3>27.2.2 页面布局<span class="hx-absolute -hx-mt-20" id="2722-页面布局"></span>
    <a href="#2722-%e9%a1%b5%e9%9d%a2%e5%b8%83%e5%b1%80" class="subheading-anchor" aria-label="Permalink for this section"></a></h3><p>与 B 树和 GiST 索引不同，SP-GiST 树节点和页面之间没有一对一的对应关系。由于内部节点通常没有太多子节点，因此多个节点必须被打包进一个单独的页面中。不同类型的节点存储在不同的页面：内部节点存储在内部页面中，而叶节点则存储在叶子页面中。</p>
<p>内部页面中存储的索引项持有用作前缀的值，以及一组指向子节点的指针；每个指针可能伴随一个标签。</p>
<p>叶子页面的条目由一个值和一个 TID 组成。</p>
<p>与特定内部节点相关的所有叶节点都存储在一个单独的页面中，并绑定成一个列表。如果页面无法容纳另一个节点，这个列表可以移动到不同的页面，<sup id="fnref:6"><a href="#fn:6" class="footnote-ref" role="doc-noteref">6</a></sup> 或者，页面也可以被分裂；无论哪种方式，列表从不会延伸至多个页面。</p>
<p>为了节省空间，算法尝试将新节点添加到同一页中，直到这些页面完全填满。最后使用的页面编号被后台进程缓存，并定期保存在零页中，称为元页面。元页面不包含指向根节点的引用，我们在 B 树中会看到根节点，而 SP-GiST 索引的根始终位于第一页。</p>
<blockquote>
<p>不幸的是，pageinspect 扩展并没有提供窥探 SP-GiST 的函数，但我们可以使用名为 gevel <sup id="fnref:7"><a href="#fn:7" class="footnote-ref" role="doc-noteref">7</a></sup> 的外部扩展。它曾试图将其功能整合到 pageinspect 中，但并未成功。<sup id="fnref:8"><a href="#fn:8" class="footnote-ref" role="doc-noteref">8</a></sup></p>
</blockquote>
<p>回到我们的例子。下面的插图显示了树节点如何在页面之间分配。quad_point_ops 操作符类实际上并不使用标签。由于一个节点最多可以有四个子节点，因此索引保留了一个固定大小的四指针数组，其中一些可能是空的。</p>
<img src="27-6.png" style="width:70%; float:left" />
<div style="clear:both;"></div>
<h3>27.2.3 搜索<span class="hx-absolute -hx-mt-20" id="2723-搜索"></span>
    <a href="#2723-%e6%90%9c%e7%b4%a2" class="subheading-anchor" aria-label="Permalink for this section"></a></h3><p>让我们用同样的例子来看一下搜索位于点 (3,7) 上方的点的算法。</p>
<img src="27-7.png" style="width:70%; float:left" />
<div style="clear:both;"></div>
<p>搜索从根节点开始。内部 consistency 函数 <sup id="fnref:9"><a href="#fn:9" class="footnote-ref" role="doc-noteref">9</a></sup> 决定了要下降的子节点。点 (3,7) 与根节点的中心点 (5,5) 进行比较，来选择可能包含所寻找点的象限；在这个例子中，是第一象限和第四象限。</p>
<p>一旦进入了具有中心点 (7,7) 的节点，我们必须再次选择要下降的子节点。它们属于第一象限和第四象限，但由于第四象限为空，我们只需要检查一个叶节点。叶节点的 consistency 函数 <sup id="fnref:10"><a href="#fn:10" class="footnote-ref" role="doc-noteref">10</a></sup> 将此节点的点与查询中指定的点 (3,7) 进行比较。只有 (8,9) 满足上述条件。</p>
<p>现在我们只需要回到上一层，并检查对应于根节点的第四象限的节点。它是空的，所以搜索就完成了。</p>
<img src="27-8.png" style="width:70%; float:left" />
<div style="clear:both;"></div>
<h3>27.2.4 插入<span class="hx-absolute -hx-mt-20" id="2724-插入"></span>
    <a href="#2724-%e6%8f%92%e5%85%a5" class="subheading-anchor" aria-label="Permalink for this section"></a></h3><p>当一个值被插入到 SP-GiST 树中时，<sup id="fnref:11"><a href="#fn:11" class="footnote-ref" role="doc-noteref">11</a></sup> 之后的每一个动作都由 choice 函数决定。<sup id="fnref:12"><a href="#fn:12" class="footnote-ref" role="doc-noteref">12</a></sup> 在这个特定的情况下，它简单地将点指向对应其象限的现有节点之一。</p>
<p>例如，让我们添加值 (7,1)：</p>
<img src="27-9.png" style="width:70%; float:left" />
<div style="clear:both;"></div>
<p>这个值属于第二象限，将被添加到相应的树节点中：</p>
<img src="27-10.png" style="width:70%; float:left" />
<div style="clear:both;"></div>
<p>如果在插入后，所选象限中的叶节点列表变得过大 (必须适应单个页面)，那么页面会分裂。picksplit 函数 <sup id="fnref:13"><a href="#fn:13" class="footnote-ref" role="doc-noteref">13</a></sup> 通过计算所有点坐标的平均值来确定新的中心点，从而或多或少均匀地在新象限之间分配子节点。</p>
<p>下图说明了由于点 (2,1) 插入而导致的页面溢出：</p>
<img src="27-11.png" style="width:70%; float:left" />
<div style="clear:both;"></div>
<p>中心点是 (1,1) 的新内部节点被添加到树中，同时点 (0,0)、(1,2) 和 (2,1) 在新象限之间重新分配：</p>
<img src="27-12.png" style="width:70%; float:left" />
<div style="clear:both;"></div>
<h3>27.2.5 属性<span class="hx-absolute -hx-mt-20" id="2725-属性"></span>
    <a href="#2725-%e5%b1%9e%e6%80%a7" class="subheading-anchor" aria-label="Permalink for this section"></a></h3><p><strong>访问方法属性</strong>。spgist 方法显示以下属性：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; SELECT a.amname, p.name, pg_indexam_has_property<span class="o">(</span>a.oid, p.name<span class="o">)</span>
</span></span><span class="line"><span class="cl">FROM pg_am a, unnest<span class="o">(</span>array<span class="o">[</span>
</span></span><span class="line"><span class="cl">  <span class="s1">&#39;can_order&#39;</span>, <span class="s1">&#39;can_unique&#39;</span>, <span class="s1">&#39;can_multi_col&#39;</span>,
</span></span><span class="line"><span class="cl">  <span class="s1">&#39;can_exclude&#39;</span>, <span class="s1">&#39;can_include&#39;</span>
</span></span><span class="line"><span class="cl"><span class="o">])</span> p<span class="o">(</span>name<span class="o">)</span>
</span></span><span class="line"><span class="cl">WHERE a.amname <span class="o">=</span> <span class="s1">&#39;spgist&#39;</span><span class="p">;</span>
</span></span><span class="line"><span class="cl"> amname <span class="p">|</span>     name      <span class="p">|</span> pg_indexam_has_property
</span></span><span class="line"><span class="cl">−−−−−−−−+−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> spgist <span class="p">|</span> can_order     <span class="p">|</span> f
</span></span><span class="line"><span class="cl"> spgist <span class="p">|</span> can_unique    <span class="p">|</span> f
</span></span><span class="line"><span class="cl"> spgist <span class="p">|</span> can_multi_col <span class="p">|</span> f
</span></span><span class="line"><span class="cl"> spgist <span class="p">|</span> can_exclude   <span class="p">|</span> t
</span></span><span class="line"><span class="cl"> spgist <span class="p">|</span> can_include   <span class="p">|</span> t
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">5</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>不支持排序和唯一性属性。也不支持多列索引。</p>
<p>支持排它约束，与 GiST 类似。</p>
<p>可以创建带有<span class="marginalia" data-note="v. 14">额外 INCLUDE 列</span>的 SP-GiST 索引。</p>
<p><strong>索引级属性</strong>。与 GiST 不同，SP-GiST 索引不支持聚簇：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; SELECT p.name, pg_index_has_property<span class="o">(</span><span class="s1">&#39;airports_quad_idx&#39;</span>, p.name<span class="o">)</span>
</span></span><span class="line"><span class="cl">FROM unnest<span class="o">(</span>array<span class="o">[</span>
</span></span><span class="line"><span class="cl">  <span class="s1">&#39;clusterable&#39;</span>, <span class="s1">&#39;index_scan&#39;</span>, <span class="s1">&#39;bitmap_scan&#39;</span>, <span class="s1">&#39;backward_scan&#39;</span>
</span></span><span class="line"><span class="cl"><span class="o">])</span> p<span class="o">(</span>name<span class="o">)</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">     name      <span class="p">|</span> pg_index_has_property
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> clusterable   <span class="p">|</span> f
</span></span><span class="line"><span class="cl"> index_scan    <span class="p">|</span> t
</span></span><span class="line"><span class="cl"> bitmap_scan   <span class="p">|</span> t
</span></span><span class="line"><span class="cl"> backward_scan <span class="p">|</span> f
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">4</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>支持以两种方式获取 TIDS (要么逐个获取，要么作为位图)。不支持反向扫描，因为这对 SP-GiST 来说没有任何意义。</p>
<p><strong>列级属性</strong>。在大多数情况下，列级属性是相同的：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; SELECT p.name,
</span></span><span class="line"><span class="cl">  pg_index_column_has_property<span class="o">(</span><span class="s1">&#39;airports_quad_idx&#39;</span>, 1, p.name<span class="o">)</span>
</span></span><span class="line"><span class="cl">FROM unnest<span class="o">(</span>array<span class="o">[</span>
</span></span><span class="line"><span class="cl">  <span class="s1">&#39;orderable&#39;</span>, <span class="s1">&#39;search_array&#39;</span>, <span class="s1">&#39;search_nulls&#39;</span>
</span></span><span class="line"><span class="cl"><span class="o">])</span> p<span class="o">(</span>name<span class="o">)</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">     name     <span class="p">|</span> pg_index_column_has_property
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> orderable    <span class="p">|</span> f
</span></span><span class="line"><span class="cl"> search_array <span class="p">|</span> f
</span></span><span class="line"><span class="cl"> search_nulls <span class="p">|</span> t
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">3</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>不支持排序，因此所有相关属性都没有任何意义，并且被禁用。</p>
<p>到目前为止我还没有提到空值，但正如我们在索引属性中看到的，是支持空值的。不同于 GiST，SP-GiST 索引不在主树中存储空值。相反，它会创建一个单独的树；它的根位于第二个索引页面。因此，前三个页面始终具有相同的含义：元页面、主树的根和空值树的根。</p>
<p>一些列级属性可能取决于特定的操作符类：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; SELECT p.name,
</span></span><span class="line"><span class="cl">  pg_index_column_has_property<span class="o">(</span><span class="s1">&#39;airports_quad_idx&#39;</span>, 1, p.name<span class="o">)</span>
</span></span><span class="line"><span class="cl">FROM unnest<span class="o">(</span>array<span class="o">[</span>
</span></span><span class="line"><span class="cl">  <span class="s1">&#39;returnable&#39;</span>, <span class="s1">&#39;distance_orderable&#39;</span>
</span></span><span class="line"><span class="cl"><span class="o">])</span> p<span class="o">(</span>name<span class="o">)</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">        name        <span class="p">|</span> pg_index_column_has_property
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> returnable         <span class="p">|</span> t
</span></span><span class="line"><span class="cl"> distance_orderable <span class="p">|</span> t
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">2</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>就像本章中的所有其他例子一样，这个索引可以用于仅索引扫描。</p>
<p>但通常来说，操作符类不一定在叶子页面中<span class="marginalia" data-note="v. 11">存储完整的值</span>，因为可以通过表重新检查它们。举个例子，这允许在 PostGIS 中使用 SP-GiST 索引来处理潜在的大型几何值。</p>
<p><span class="marginalia" data-note="v. 12">支持最近邻搜索</span>；我们已经在操作符类中看到了排序操作符 &lt;-&gt;。</p>
<h2>27.3 点的 K 维树<span class="hx-absolute -hx-mt-20" id="273-点的-k-维树"></span>
    <a href="#273-%e7%82%b9%e7%9a%84-k-%e7%bb%b4%e6%a0%91" class="subheading-anchor" aria-label="Permalink for this section"></a></h2><p>平面上的点也可以使用另一种分区方法进行索引：我们可以将平面分成两个子区域，而不是四个。这种分区由 kd_point_ops <sup id="fnref:14"><a href="#fn:14" class="footnote-ref" role="doc-noteref">14</a></sup>  操作符类实现：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; CREATE INDEX airports_kd_idx ON airports_big
</span></span><span class="line"><span class="cl">USING spgist<span class="o">(</span>coordinates kd_point_ops<span class="o">)</span><span class="p">;</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>请注意，索引值、前缀和标签可能具有不同的数据类型。对于这个操作符类，值表示为点，前缀是实数，而没有提供标签 (如 quad_point_ops 中的)。</p>
<p>让我们在 Y 轴上选择某个坐标 (它在示例中定义了纬度，与机场相对应)。这个坐标将平面分为两个子区域，上区域和下区域：</p>
<img src="27-13.png" style="width:80%; float:left" />
<div style="clear:both;"></div>
<p>对于这些子区域中的每一个，选择 X 轴 (经度) 上的坐标，将它们分成左右两个子区域：</p>
<img src="27-14.png" style="width:80%; float:left" />
<div style="clear:both;"></div>
<p>我们将继续分割每一个得到的子区域，轮流进行水平和垂直划分，直到每个部分中的点适应单一索引页为止：</p>
<img src="27-15.png" style="width:80%; float:left" />
<div style="clear:both;"></div>
<p>以这种方式构建的树的所有内部叶节点将只有两个子节点。这种方法可以很容易地推广到任意维度的空间，因此这样的树通常被称为 k 维树 (k-D 树)。</p>
<h2>27.4 字符串的基数树<span class="hx-absolute -hx-mt-20" id="274-字符串的基数树"></span>
    <a href="#274-%e5%ad%97%e7%ac%a6%e4%b8%b2%e7%9a%84%e5%9f%ba%e6%95%b0%e6%a0%91" class="subheading-anchor" aria-label="Permalink for this section"></a></h2><p>SP-GiST 的 text_ops 操作符类为字符串实现了基数树。<sup id="fnref:15"><a href="#fn:15" class="footnote-ref" role="doc-noteref">15</a></sup> 在这里，内部节点的前缀确实是一个前缀，它是所有子节点中字符串的共同部分。</p>
<p>指向子节点的指针由前缀后面的值的第一个字节标记。</p>
<blockquote>
<p>为清楚起见，我使用单个字符来表示前缀，但这仅适用于 8 字节编码。通常，操作符类将字符串作为字节序进行处理。此外，前缀可以取几个具有特殊语义的其他值，因此每个前缀实际上分配了两个字节。</p>
</blockquote>
<p>子节点存储前缀和标签后面的部分值。叶节点只保留后缀。</p>
<p>这是一个基于几个名称构建的基数树的例子：</p>
<img src="27-16.png" style="width:70%; float:left" />
<div style="clear:both;"></div>
<p>为了重构叶子页面中索引键的完整值，我们可以从根节点开始，连接所有的前缀和标签。</p>
<h3>27.4.1 操作符类<span class="hx-absolute -hx-mt-20" id="2741-操作符类"></span>
    <a href="#2741-%e6%93%8d%e4%bd%9c%e7%ac%a6%e7%b1%bb" class="subheading-anchor" aria-label="Permalink for this section"></a></h3><p>text_ops 操作符类支持通常用于 ordinal 数据类型的比较操作符，包括文本字符串：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; SELECT oprname, oprcode::regproc, amopstrategy
</span></span><span class="line"><span class="cl">FROM pg_am am
</span></span><span class="line"><span class="cl">  JOIN pg_opclass opc ON <span class="nv">opcmethod</span> <span class="o">=</span> am.oid
</span></span><span class="line"><span class="cl">  JOIN pg_amop amop ON <span class="nv">amopfamily</span> <span class="o">=</span> opcfamily
</span></span><span class="line"><span class="cl">  JOIN pg_operator opr ON opr.oid <span class="o">=</span> amopopr
</span></span><span class="line"><span class="cl">WHERE <span class="nv">amname</span> <span class="o">=</span> <span class="s1">&#39;spgist&#39;</span>
</span></span><span class="line"><span class="cl">AND <span class="nv">opcname</span> <span class="o">=</span> <span class="s1">&#39;text_ops&#39;</span>
</span></span><span class="line"><span class="cl">ORDER BY amopstrategy<span class="p">;</span>
</span></span><span class="line"><span class="cl"> oprname <span class="p">|</span>     oprcode     <span class="p">|</span> amopstrategy
</span></span><span class="line"><span class="cl">−−−−−−−−−+−−−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> ~&lt;~     <span class="p">|</span> text_pattern_lt <span class="p">|</span>            <span class="m">1</span>
</span></span><span class="line"><span class="cl"> ~&lt;<span class="o">=</span>~    <span class="p">|</span> text_pattern_le <span class="p">|</span>            <span class="nv">2</span>
</span></span><span class="line"><span class="cl"> <span class="o">=</span>       <span class="p">|</span> texteq          <span class="p">|</span>            <span class="m">3</span>
</span></span><span class="line"><span class="cl"> ~&gt;<span class="o">=</span>~    <span class="p">|</span> text_pattern_ge <span class="p">|</span>            <span class="m">4</span>
</span></span><span class="line"><span class="cl"> ~&gt;~     <span class="p">|</span> text_pattern_gt <span class="p">|</span>            <span class="m">5</span>
</span></span><span class="line"><span class="cl"> &lt;       <span class="p">|</span> text_lt         <span class="p">|</span>           <span class="m">11</span>
</span></span><span class="line"><span class="cl"> &lt;<span class="o">=</span>      <span class="p">|</span> text_le         <span class="p">|</span>           <span class="m">12</span>
</span></span><span class="line"><span class="cl"> &gt;<span class="o">=</span>      <span class="p">|</span> text_ge         <span class="p">|</span>           <span class="m">14</span>
</span></span><span class="line"><span class="cl"> &gt;       <span class="p">|</span> text_gt         <span class="p">|</span>           <span class="m">15</span>
</span></span><span class="line"><span class="cl"> ^@      <span class="p">|</span> starts_with     <span class="p">|</span>           <span class="m">28</span>
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">10</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>常规操作符处理字符，而带波浪号的操作符处理字节。它们不考虑排序规则 (就像 B 树的 text_pattern_ops 操作符类)，所以它们可以用来加速 LIKE 条件的搜索：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; CREATE INDEX tickets_spgist_idx ON tickets
</span></span><span class="line"><span class="cl">  USING spgist<span class="o">(</span>passenger_name<span class="o">)</span><span class="p">;</span>
</span></span><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN <span class="o">(</span>costs off<span class="o">)</span> SELECT *
</span></span><span class="line"><span class="cl">FROM tickets
</span></span><span class="line"><span class="cl">WHERE passenger_name LIKE <span class="s1">&#39;IVAN%&#39;</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">                       QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl">Bitmap Heap Scan on tickets
</span></span><span class="line"><span class="cl">  Filter: <span class="o">(</span>passenger_name ~~ <span class="s1">&#39;IVAN%&#39;</span>::text<span class="o">)</span>
</span></span><span class="line"><span class="cl">  −&gt; Bitmap Index Scan on tickets_spgist_idx
</span></span><span class="line"><span class="cl">      Index Cond: <span class="o">((</span>passenger_name ~&gt;<span class="o">=</span>~ <span class="s1">&#39;IVAN&#39;</span>::text<span class="o">)</span> AND
</span></span><span class="line"><span class="cl">      <span class="o">(</span>passenger_name ~&lt;~ <span class="s1">&#39;IVAO&#39;</span>::text<span class="o">))</span>
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">5</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<blockquote>
<p>如果将常规操作符 &gt;= 和 &lt; 与 &ldquo;C&rdquo; 以外的排序规则一起使用，那么索引实际上变得毫无用处，因为它处理的是字节而不是字符。</p>
</blockquote>
<p>对于这种<span class="marginalia" data-note="v. 11">前缀搜索</span>的情况，操作符类提供了更为合适的 ^@ 操作符：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; EXPLAIN <span class="o">(</span>costs off<span class="o">)</span> SELECT *
</span></span><span class="line"><span class="cl">FROM tickets
</span></span><span class="line"><span class="cl">WHERE passenger_name ^@ <span class="s1">&#39;IVAN&#39;</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">                     QUERY PLAN
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl">Bitmap Heap Scan on tickets
</span></span><span class="line"><span class="cl">  Recheck Cond: <span class="o">(</span>passenger_name ^@ <span class="s1">&#39;IVAN&#39;</span>::text<span class="o">)</span>
</span></span><span class="line"><span class="cl">  −&gt; Bitmap Index Scan on tickets_spgist_idx
</span></span><span class="line"><span class="cl">      Index Cond: <span class="o">(</span>passenger_name ^@ <span class="s1">&#39;IVAN&#39;</span>::text<span class="o">)</span>
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">4</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>基数树的表示有时会比 B 树更为紧凑，因为它不存储完整的值：它会在遍历树的时候根据需要重建这些值。</p>
<h3>27.4.2 搜索<span class="hx-absolute -hx-mt-20" id="2742-搜索"></span>
    <a href="#2742-%e6%90%9c%e7%b4%a2" class="subheading-anchor" aria-label="Permalink for this section"></a></h3><p>让我们在 names 表上运行以下查询：</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl">SELECT *
</span></span><span class="line"><span class="cl">FROM names
</span></span><span class="line"><span class="cl">WHERE name ~&gt;<span class="o">=</span>~ <span class="s1">&#39;VALERIY&#39;</span>
</span></span><span class="line"><span class="cl">  AND name ~&lt;~ <span class="s1">&#39;VLADISLAV&#39;</span><span class="p">;</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>首先，在根节点上调用内部 consistency 函数 <sup id="fnref:16"><a href="#fn:16" class="footnote-ref" role="doc-noteref">16</a></sup>，以确定要下降的子节点。这个函数将前缀 V 与标签 A 和 L 连接起来。接收到的值 VA 进入查询条件；字符串字面量在那里被截断，以确保它们的长度不会超过正在检查的值的长度：VA ~ &gt;=~ &lsquo;VA&rsquo; and VA ~ &lt;~ &lsquo;VL&rsquo;。条件满足，所以需要检查带标签 A 的子节点。值 VL 以同样的方式检查。它也是一个匹配项，所以也需要检查带标签 L 的节点。</p>
<p>现在让我们取与值 VA 对应的节点。它的前缀是空的，所以对于三个子节点，内部 consistency 函数通过连接在前一步接收到的 VA 和标签，重构值 VAD、VAL 和 VAS。条件 VAD ~ &gt;=~ &lsquo;VAL&rsquo; and VAD ~ &lt;~ &lsquo;VER&rsquo; 不成立，但其他两个值是合适的。</p>
<p>当以这种方式遍历树时，算法会过滤掉不匹配的分支，并到达叶节点。叶节点的 consistency 函数检查在遍历树期间重建的值是否满足查询条件。匹配的值作为索引扫描的结果返回。</p>
<img src="27-17.png" style="width:70%; float:left" />
<div style="clear:both;"></div>
<p>请注意，虽然查询使用了大于和小于操作符，这些操作符对于 B 树来说很常见，但是通过 SP-GiST 进行范围搜索的效率要低得多。在 B 树中，下降到范围的一个边界值，然后扫描叶子页面列表就足够了。</p>
<h3>27.4.3 插入<span class="hx-absolute -hx-mt-20" id="2743-插入"></span>
    <a href="#2743-%e6%8f%92%e5%85%a5" class="subheading-anchor" aria-label="Permalink for this section"></a></h3><p>点的操作符类的 choice 函数总是可以将一个新值导向一个现有子区域之一 (一个象限或其中的一半)。但对于基数树来说并非如此：新值可能与任何现有的前缀都不匹配，在这种情况下必须分裂内部节点。</p>
<p>让我们将名称 VLADA 添加到一个已经创建的树中。</p>
<p>choice 函数 <sup id="fnref:17"><a href="#fn:17" class="footnote-ref" role="doc-noteref">17</a></sup> 成功地从根节点下降到下一个节点 ( V+L )，但值的剩余部分 ADA 与 ADI 前缀不匹配。节点必须被分成两部分：其中一个结果节点将包含公共部分的前缀 (AD)，而前缀的其余部分将被下移一级：</p>
<img src="27-18.png" style="width:70%; float:left" />
<div style="clear:both;"></div>
<div style="clear:both;"></div>
<p>然后，再次在同一节点上调用 choice 函数。前缀现在对应于该值，但是没有带有合适标签 (A) 的子节点，所以函数决定创建这样一个节点。最终结果如下图所示；在插入过程中添加或修改的节点会高亮显示。</p>
<img src="27-19.png" style="width:70%; float:left" />
<div style="clear:both;"></div>
<h3>27.4.4 属性<span class="hx-absolute -hx-mt-20" id="2744-属性"></span>
    <a href="#2744-%e5%b1%9e%e6%80%a7" class="subheading-anchor" aria-label="Permalink for this section"></a></h3><p>我已经在上面描述了访问方法和索引级属性；它们对所有类都是通用的。大多数列级属性也保持不变。</p>
<div class="hextra-code-block hx-relative hx-mt-6 first:hx-mt-0 hx-group/code">
  

<div><div class="highlight"><pre tabindex="0" class="chroma"><code class="language-bash" data-lang="bash"><span class="line"><span class="cl"><span class="o">=</span>&gt; SELECT p.name,
</span></span><span class="line"><span class="cl">  pg_index_column_has_property<span class="o">(</span><span class="s1">&#39;tickets_spgist_idx&#39;</span>, 1, p.name<span class="o">)</span>
</span></span><span class="line"><span class="cl">FROM unnest<span class="o">(</span>array<span class="o">[</span>
</span></span><span class="line"><span class="cl">  <span class="s1">&#39;returnable&#39;</span>, <span class="s1">&#39;distance_orderable&#39;</span>
</span></span><span class="line"><span class="cl"><span class="o">])</span> p<span class="o">(</span>name<span class="o">)</span><span class="p">;</span>
</span></span><span class="line"><span class="cl">        name        <span class="p">|</span> pg_index_column_has_property
</span></span><span class="line"><span class="cl">−−−−−−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
</span></span><span class="line"><span class="cl"> returnable         <span class="p">|</span> t
</span></span><span class="line"><span class="cl"> distance_orderable <span class="p">|</span> f
</span></span><span class="line"><span class="cl"><span class="o">(</span><span class="m">2</span> rows<span class="o">)</span></span></span></code></pre></div></div><div class="hextra-code-copy-btn-container hx-opacity-0 hx-transition group-hover/code:hx-opacity-100 hx-flex hx-gap-1 hx-absolute hx-m-[11px] hx-right-0 hx-top-0">
  <button
    class="hextra-code-copy-btn hx-group/copybtn hx-transition-all active:hx-opacity-50 hx-bg-primary-700/5 hx-border hx-border-black/5 hx-text-gray-600 hover:hx-text-gray-900 hx-rounded-md hx-p-1.5 dark:hx-bg-primary-300/10 dark:hx-border-white/10 dark:hx-text-gray-400 dark:hover:hx-text-gray-50"
    title="Copy code"
  >
    <div class="copy-icon group-[.copied]/copybtn:hx-hidden hx-pointer-events-none hx-h-4 hx-w-4"></div>
    <div class="success-icon hx-hidden group-[.copied]/copybtn:hx-block hx-pointer-events-none hx-h-4 hx-w-4"></div>
  </button>
</div>

  
</div>
<p>即使索引值未显式存储在树中，也支持仅索引扫描，因为在从根节点到叶节点的遍历过程中可以重建值。</p>
<p>至于距离操作符，它没有为字符串定义，所以这个操作符类没有提供最近邻搜索。</p>
<blockquote>
<p>这并不意味着无法为字符串实现距离的概念。例如，pg_trgm 扩展添加了一个基于三元组的距离操作符：在两个字符串中找到的公共三元组越少，它们彼此之间被认为的距离就越远。还有莱文斯坦距离，它被定义为将一个字符串转换为另一个字符串所需的最少单字符编辑次数。fuzzystrmatch 扩展中提供了计算这种距离的函数。但这些扩展都没有提供带有 SP-GiST 支持的操作符类。</p>
</blockquote>
<h2>27.5 其他数据类型<span class="hx-absolute -hx-mt-20" id="275-其他数据类型"></span>
    <a href="#275-%e5%85%b6%e4%bb%96%e6%95%b0%e6%8d%ae%e7%b1%bb%e5%9e%8b" class="subheading-anchor" aria-label="Permalink for this section"></a></h2><p>SP-GiST 操作符类不仅限于我们上面讨论的索引点和文本字符串。</p>
<p><strong>几何类型</strong>。box_ops <sup id="fnref:18"><a href="#fn:18" class="footnote-ref" role="doc-noteref">18</a></sup> 操作符类实现了一个用于矩形的四叉树。矩形由四维空间中的点表示，所以区域被划分为十六个分区。</p>
<p><span class="marginalia" data-note="v. 11">poly_ops</span> 类可用于索引多边形。它是一个模糊操作符类：它实际上使用的是边界框而不是多边形，就像 box_ops 一样，然后通过表重新检查结果。</p>
<p>选择 GiST 还是 SP-GiST 在很大程度上取决于要索引的数据性质。例如，PostGIS 文档推荐对于具有大量重叠的对象 (也称为&quot;意大利面数据&quot;) 使用 SP-GiST 索引。<sup id="fnref:19"><a href="#fn:19" class="footnote-ref" role="doc-noteref">19</a></sup></p>
<p><strong>范围类型</strong>。用于范围的四叉树提供了 range_ops 操作符类。<sup id="fnref:20"><a href="#fn:20" class="footnote-ref" role="doc-noteref">20</a></sup> 一个区间由二维点定义：X 轴表示下边界，而 Y 轴表示上边界。</p>
<p><strong>网络地址类型</strong>。对于 inet 数据类型，inet_ops4 <sup id="fnref:21"><a href="#fn:21" class="footnote-ref" role="doc-noteref">21</a></sup> 操作符类实现了一个基数树。</p>
<div class="footnotes" role="doc-endnotes">
<hr>
<ol>
<li id="fn:1">
<p>postgresql.org/docs/14/spgist.html<br>backend/access/spgist/README&#160;<a href="#fnref:1" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:2">
<p>backend/access/spgist/spgscan.c, spgWalk function&#160;<a href="#fnref:2" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:3">
<p>postgresql.org/docs/14/spgist-extensibility.html&#160;<a href="#fnref:3" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:4">
<p>backend/access/spgist/spgquadtreeproc.c&#160;<a href="#fnref:4" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:5">
<p>include/access/stratnum.h&#160;<a href="#fnref:5" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:6">
<p>backend/access/spgist/spgdoinsert.c, moveLeafs function&#160;<a href="#fnref:6" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:7">
<p>sigaev.ru/git/gitweb.cgi?p=gevel.git&#160;<a href="#fnref:7" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:8">
<p>commitfest.postgresql.org/15/1207&#160;<a href="#fnref:8" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:9">
<p>backend/access/spgist/spgquadtreeproc.c, spg_quad_inner_consistent function&#160;<a href="#fnref:9" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:10">
<p>backend/access/spgist/spgquadtreeproc.c, spg_quad_leaf_consistent function&#160;<a href="#fnref:10" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:11">
<p>backend/access/spgist/spgdoinsert.c, spgdoinsert function&#160;<a href="#fnref:11" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:12">
<p>backend/access/spgist/spgquadtreeproc.c, spg_quad_choose function&#160;<a href="#fnref:12" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:13">
<p>backend/access/spgist/spgquadtreeproc.c, spg_quad_picksplit function&#160;<a href="#fnref:13" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:14">
<p>backend/access/spgist/spgkdtreeproc.c&#160;<a href="#fnref:14" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:15">
<p>backend/access/spgist/spgtextproc.c&#160;<a href="#fnref:15" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:16">
<p>backend/access/spgist/spgtextproc.c, spg_text_inner_consistent function&#160;<a href="#fnref:16" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:17">
<p>backend/access/spgist/spgtextproc.c, spg_text_choose function&#160;<a href="#fnref:17" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:18">
<p>backend/utils/adt/geo_spgist.c&#160;<a href="#fnref:18" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:19">
<p>postgis.net/docs/using_postgis_dbmanagement.html#spgist_indexes&#160;<a href="#fnref:19" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:20">
<p>backend/utils/adt/rangetypes_spgist.c&#160;<a href="#fnref:20" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
<li id="fn:21">
<p>backend/utils/adt/network_spgist.c&#160;<a href="#fnref:21" class="footnote-backref" role="doc-backlink">&#x21a9;&#xfe0e;</a></p>
</li>
</ol>
</div>

        </div>
        <div class="hx-mt-16"></div>
        
        
      </main>
    </article>
  </div>

      <footer class="hextra-footer hx-bg-gray-100 hx-pb-[env(safe-area-inset-bottom)] dark:hx-bg-neutral-900 print:hx-bg-transparent"><div
    class="hx-max-w-screen-xl hx-mx-auto hx-flex hx-justify-center hx-py-12 hx-pl-[max(env(safe-area-inset-left),1.5rem)] hx-pr-[max(env(safe-area-inset-right),1.5rem)] hx-text-gray-600 dark:hx-text-gray-400 md:hx-justify-start"
  >
    <div class="hx-flex hx-w-full hx-flex-col hx-items-center sm:hx-items-start"><div class="hx-mt-6 hx-text-xs">本中文译文版权归熊灿灿所有。英文原文版权归 Postgres Professional 所有。本译文根据授权翻译与发布。</div>
    </div>
  </div>
</footer>
    
    <script defer src="/js/main.js" integrity=""></script>


<script defer src="/lib/flexsearch/flexsearch.bundle.min.0425860527cc9968f9f049421c7a56b39327d475e2e3a8f550416be3a9134327.js" integrity="sha256-BCWGBSfMmWj58ElCHHpWs5Mn1HXi46j1UEFr46kTQyc="></script>
    <script defer src="/en.search.js" integrity=""></script>
<link type="text/css" rel="stylesheet" href="/lib/katex/katex.min.7e5db7914b97e596a36c1abb67ccc7f174f8bb71d38c9a88c55b262ed1737f97.css" integrity="sha256-fl23kUuX5ZajbBq7Z8zH8XT4u3HTjJqIxVsmLtFzf5c=" />
  <script defer src="/lib/katex/katex.min.9f45307c5794ed247a0d095f3a62e52ef2215a67b2327203a7fd919959ae79d1.js" integrity="sha256-n0UwfFeU7SR6DQlfOmLlLvIhWmeyMnIDp/2RmVmuedE="></script>
  <script defer src="/lib/katex/auto-render.min.7b57d427ac6270677daf8d8380ded2cc73336f9149a167b8e1fe0d6ef66604ae.js" integrity="sha256-e1fUJ6xicGd9r42DgN7SzHMzb5FJoWe44f4NbvZmBK4="></script>
  <script defer src="/lib/katex/mhchem.min.f0ca03df194b8c3d6017ff455db6a0ef98857905663fa311a6cded788b15340b.js" integrity="sha256-8MoD3xlLjD1gF/9FXbag75iFeQVmP6MRps3teIsVNAs="></script>
  <script>
    
    
    document.addEventListener("DOMContentLoaded", function () {
      renderMathInElement(document.body, {
        delimiters: [
          { left: "$$", right: "$$", display: true },
          { left: "$", right: "$", display: false },
          { left: "\\(", right: "\\)", display: false },
          { left: "\\begin{equation}", right: "\\end{equation}", display: true },
          {left: "\\begin{align}", right: "\\end{align}", display: true},
          {left: "\\begin{alignat}", right: "\\end{alignat}", display: true},
          {left: "\\begin{gather}", right: "\\end{gather}", display: true},
          {left: "\\begin{CD}", right: "\\end{CD}", display: true},
          { left: "\\[", right: "\\]", display: true },
        ],
        throwOnError: false,
      });
    });
  </script>


  </body>
</html>
